1. Field of the Invention
The present invention relates to the field of digital adders, and more specifically to digital adders using a carry look-ahead technique.
2. Discussion of the Related Art
FIG. 1 schematically and partially shows a conventional carry look-ahead 8-bit adder that calculates A+B=S where, A, B, and S are coded over eight bits. A first block 1 of the adder includes eight identical cells 11, each having two inputs and one pair of outputs. A cell 11 of rank i is connected to receive on its first input bit Ai and on its second input bit Bi. It generates a first signal Pi such that Pi=Ai+Bi and an output signal Gi such that Gi=Aixe2x80xa2Bi. A second block of the adder receives the 8 couples of signals {P1, G1} to {P8, G8} coming from block 1. Block 2 is formed of identical elementary cells 21 connected to calculate from the eight signal couples {P1, G1} to {P8, G8}, eight couples of output signals {p1, g15} to {p8, g8}. If k is included between 2 and 8, pk is such that             p      k        =                  π                  i          =          1                    ⁢              xe2x80x83            ⁢              P        i              ,            with      ⁢              xe2x80x83            ⁢              p        1              =          P      1      
and gk is such that             g      k        =                            ∑                      i            =            1                                k            -            1                          ⁢                  xe2x80x83                ⁢                  (                                    G              i                        ⁢                          π                              j                =                                  i                  +                  1                                            k                        ⁢                          xe2x80x83                        ⁢                          P              j                                )                    +              G        k              ,            with      ⁢              xe2x80x83            ⁢              g        1              =          G      1      
The 8 couples {p1, g1} to {p8, g8} generated by block 2 allow calculation of sum S such that A+B=S. If C0 is the entering carry of operation A+B, each term Si of sum S is given by Sk=(C0xe2x80xa2Pk-1+gk-1)⊕Ak⊕Bk, with S1=C0⊕Ak⊕Bk. Similarly, if Cn is the exiting carry of operation A+B, Cn is given by Cn=C0xe2x80xa2pn+gn. The calculation of terms Sk and Cn is performed by a block 3 of the adder, the structure of which is well known in the art.
An elementary cell 21 includes two input couples {E1, E2} and {E3, E4} and an output couple {O1, O2}. Output O1 is such that O1=E1. E3 and output O2 is such that O2=E2. E4+E3. It should be noted that no cell 21 is required to calculate couple {p1, g1} since {p1, g1}={P1, G1}. Conversely, a cell 21 is required to calculate {p2, g2} from {P1, G1} and {P2, G2}. Similarly, an additional cell 21 is required to calculate {p3, g3} from {p2, g2} and {P3, G3}.
The adder considered is an 8-bit adder. 8=23, and it can be considered that block 2 is organized in a array of eight rows and three columns, a location of the array being occupied by a cell 21 or left empty. It should be noted that cells 21 of the third column of block 2 receive on their first input couple {E1, E2} the output couple {O1, O2} generated by the last cell 21 of the first half of the second column of block 2.
Similarly, considering a 16-bit adder, block 2 of the 16-bit adder include comprise four columns and sixteen rows, and the eight cells of the fourth column of block 2 would receive on their first input couple {E1, E2} the output couple {O1, O2} of the last cell 21 of the first half of the third column.
A major disadvantage of this architecture is that it includes a critical path in which a successive cell 21 controls twice as many cells as the preceding cell. More specifically, a cell 11 controls a single cell of the first column. Some cells of the first column each control two cells of the second column. Some cells of the second column each control four cells of the third column, etc. In order not to increase the propagation time between a first cell which controls n cells and one of these n cells, the fan-out of the first cell must be n, that is, the output transistors of the first cell must have a size n times higher than the minimum size. However, the size increase of the output transistors of a cell increases the propagation time of a cell, since the gate capacitances of these transistors are higher and take longer to be charged. Thus, it will not be possible to make the propagation time of a critical path as small as that of a non-critical path, lest the size of all the transistors on the critical path is adapted, which is practically impossible to implement.
Further, the circuit will include cells 21 of identical function but of different sizes. These cells 21 of different sizes will have to be created in a special library of a design system, which increases the number of cells to be managed by the designer.
Similarly, at the design of an adder, the physical implantation of the various cells 21 will have to be performed with great care to best optimize the critical path propagation time.
An object of the present invention is to provide an architecture that implements a carry look-ahead adder having a particularly fast operation.
Another object of the present invention is to provide such an adder which does not occupy a greater surface area than a conventional carry look-ahead adder.
Another object of the present invention is to provide such an adder architecture which simplifies the management of a design system library.
These objects as well as others are achieved by a digital adder that adds a first n-bit operand A and a second n-bit operand B, with n=2m, comprising:
a first block calculating couples of signals Pq and Gq based on the bits of rank q, Aq and Bq, of the first and second operand, with Pq=Aq+Bq and Gq=Aqxe2x80xa2Bq;
a second block formed of an array of elementary cells of identical functions arranged in n rows and m columns, an elementary cell having two inputs couples {E1, E2]} and {E3, E4} and one output couples {O1, O2}, providing O1=E1xe2x80xa2E3 and O2=E2xe2x80xa2E4+E3;
a normal elementary cell, that is, of a column i and of a row j, j being included between k2ixe2x88x922i-1+1 and k2i, with k varying between 1 and 2m-i, receiving:
on its first input couple, couple {Pj-1, Gj-1} if i=1 and the output couple coming from the elementary cell of column i-1 and of row (k-1)2i+1 otherwise,
on its second input couple, couple {Pj, Gj} if j=k2ixe2x88x922i-1+1 or i=1, or the output couple coming from the elementary cell of row j and of the column r+1, r being defined so that 2r+1xe2x89xa6jxe2x88x92(kxe2x88x921)2ixe2x88x922i-1xe2x89xa62r+1 otherwise; and
an auxiliary elementary cell, that is, of a column i and of a row j, j being included between (kxe2x88x921)2i+1 and k2ixe2x88x922i-30 1, having its inputs and outputs connected in parallel with those of the elementary cells corresponding to a same value of k and of i, receiving:
on its first input couple, couple {Pj, Gj} if i=1 and the output couple coming from the elementary cell of column ixe2x88x921 and of row (kxe2x88x921)2i+1 otherwise, and
on its second input couple, couple {Pj+1, Gj+1} if i=1 and the output couple coming from the elementary cell of column ixe2x88x921 and of row k2ixe2x88x922i-1+1.
According to an embodiment of the present invention, the normal cells have a lower size than the auxiliary cells.
According to another embodiment of the present invention, the digital adder comprises means for, at least in the column of highest rank, selecting as an output the output couples of the normal cells or the second input couples of these cells.
The foregoing objects, features and advantages of the present invention will be discussed in detail in the following non-limiting description of specific embodiments in connection with the accompanying drawings.